Systems for secure communications rely on cryptographic techniques to ensure that communications within the system are available to authenticated users only. Generally, a message is encrypted with a cryptographic key so that only authenticated users can decrypt the message. Even in the simplest case of a single user, the protocol for providing the proper key to the proper user can be rather elaborate. In a network having multiple authorized users with various sending and receiving privileges, the distribution and management of cryptographic keys can be quite complicated.
Some key management protocols for group-shared keys employ the so-called Wallner tree, more generally known as a “key tree”. Key trees are of major importance for key management of group-communications, such as IP multicast and application-layer group transmissions. In a key tree, a hierarchy of cryptographic keys is created based on a special selected mathematical function. The key for a given node in the tree is derived from the key of its parent node, and the keys for its children nodes are derived from itself. An example of a mathematical function used to form a key tree is the one-way hash function (OWHF), where a ChildKey=OWHF(ParentKey). Specific systems using a key tree approach are described, for example, in D. M. Wallner, E. Harder, R. C. Agee, Key Management for Multicast: Issues and Architectures, September 1998; and C. K. Wong, M. Gouda and S. Lam, “Secure Group Communications Using Key Graphs”, in Proceedings of SIGCOMM'98, which are incorporated herein by reference.
An example of a key tree is shown in FIG. 1, where the solid points represent 9 authorized entities (a root and eight users U1, U2, . . . , U8). In this structure, each of the eight users has an associated private key (K1, K2, . . , K8) that is known only to the owning user and the root. In this specific structure, the private key typically is used for private communications between the root and the respective user (unicast).
A key tree is a logical tree, meaning that the keys of the internal nodes are shared by the root and by some of the users. For example, a user may know all the keys on the tree starting from its position at a leaf node, back up the internal nodes directly to the root. Thus, in FIG. 1 for example, user U2 knows its own private key K2, and keys X3 and X1. User U4 knows K4 (its own key), X4 and X1, while User U6 knows keys K6, X5 and X2.
One typical use of a key tree is for management of a Traffic Encryption Key (TEK) that is used for the encryption of data being multicasted to a group, and a Key Encryption Key (KEK) for encrypting the TEK when the TEK is transmitted. The root is typically assigned to hold the TEK and the KEK, and it uses the keys within the key tree to send the encrypted TEK either to all the users on the tree, or only to specific selected users. Thus, assuming the TEK is to be multicasted to the entire group, the Root would simply encrypt the TEK under the KEK and send the encrypted TEK to the multicast address of the group. Non-members may be able to snoop the packet, but they will not be able to decrypt that packet containing the encrypted TEK. To send the TEK or KEK to a subset of the entire group (for example, users U1, U2, U3 and U4 in FIG. 1), the root can use key X1 to encrypt the designated TEK or KEK, and multicast the ciphertext to the entire group in a single message. The other users (U5, U6, U7 and U8 in FIG. 1) will simply drop that packet since they will not be able to decrypt it.
At first, it might appear simpler to associate a single key with each user and manage each of these individual keys as required. But, for each user in a large group to be able to communicate with each of the other users, all users must have the keys for all of the other users. This is a significant management problem that involves the distribution of large numbers of keys and substantial storage requirements; a problem made even more difficult when accounting for factors such as adding and deleting members of the group. The logical hierarchy of the key tree and the encryption keys associated with higher level nodes means that key management can use fewer and smaller messages containing fewer keys broadcast over the network using less bandwidth than would be possible with the simpler scheme.
From the above example, it is easy to see that key trees are useful for the management of cryptographic keys within groups. Currently, efforts are underway in the IETF to standardize group key protocols.
In another application, a key tree may be used for pay-per-view type subscription services as described, for example, in B. Briscoe, Zero Side Effect Multicast Key Management using Arbitrarily Revealed Key Sequences, BT Labs Report 1999, which is incorporated herein by reference. Rather than each leaf node of the tree being a user or a member of a group, the leaf nodes represent points across time. In this application, each key tree is associated with a channel or programmed unit. A subscriber pays ahead of time for the amount of programming that he or she wishes to receive in that channel. The selected amount of time determines which set of keys is given to the subscriber. To prevent illegal copying of keys by subscribers, a tamper-proof set-top box is deployed to store the keys.
Thus, as shown in FIG. 2, when a subscriber S1 wants to watch a pay-per-view channel from time t1 to t3, his set-top box must be loaded with keys X3 and K3 (the box can compute keys K1 and K3 from X3). When another subscriber wants to watch the same channel from time t4 to t7, his set-top box must be loaded with keys K4, X5 and K7 only (to prevent viewing of the channel before time t4 and after time t7). In a commercial pay-per-view environment, there will typically be one tree for each channel, and for each channel the breadth of the tree will be subject to a number of factors, including the impact of lost keys, the number of viewers, and others.
Thus, key trees are known to be useful for distributing cryptographic communications keys to multiple users in a computer network, and for communication limited to predefined blocks of time.